Making CRDTs Byzantine fault tolerant
ビザンチンノードが正しいノードより多いシステムでも、CRDTの一貫性を保つことができる
既存のCRDTに少しばかりの変更を加えるだけでOK
Operation-basedなCRDT
背景
既存のCRDTはP2Pシステムを想定しているにも関わらず、ビザンチン障害耐性がない
最終的な操作(or state)の配信が期待できるか? 間にビザンチンノードがいると、達成できない
同じバージョンベクタを持つ異なる操作(or state)を複数送信してくるビザンチンノードがいた場合、困る
不正な更新を送り付けてくるビザンチンノードがいるかもしれない
プロトコルに明らかに沿っていない場合弾けるケースもあるけど、先行する操作に依存する操作など、受け入れてしまい収束しなくなってしまう場合もある
システムモデル
キーとしては、メッセージの配信が保証できて、かつ不正な更新操作を送れなければいいよね、ということkekeho.icon
全ノードが対等なP2P
各ノードは、ノードの全体集合を知らない、頻繁に参加したり離脱したりする
ビザンチンな挙動をするノードがいる
クラッシュもビザンチンな挙動もしないやつを正しいノードとする
メッセージは有限回の再試行のあとに受信される
暗号学的にメッセージを認証することで、2つの正しいノードが直接通信する場合メッセージは破損していないものとみなせる
いい感じに正しいノードpと正しいノードqが直接通信できると仮定
間が全員Byzantineなノードだとダメなので
Byzantineノードの数が1/3以下の状況しか許容できない
投票をするらしい
仕組み
hash graphの構築
$ u: 更新
$ H: 暗号学的ハッシュ関数。耐衝突性を持つ
$ H(u): 更新のID
すべての更新$ uは、因果的に先行するハッシュのセットを含む
同じノードが生成した最後の更新のハッシュ・最後の更新以降に他のノードから受け取った更新のハッシュが含まれる。直前のだけ含めればいい。
同じノードが生成した最後の更新のハッシュ
最後の更新以降に他のノードから受信した更新のハッシュ
他の依存関係を介して辿れる依存関係は先行ハッシュのセットに含めないことで、小さなセットを保てる
DAGが形成される
head: 先頭の更新。他の更新の依存先になっていないやつ。leafのことkekeho.icon
各ノードは、DAG全体のコピーをローカルに保持する
Eventual Deliveryの担保
各ノードは、現在のヘッドを教え合い、同一だったら持っているDAGが一緒とみなせる
一致しない場合、グラフ探索を行い、どの部分まで共通しているのかを調べ、欠けている部分を送り合う
これで、過去もらえなかった更新があったとしても取ってこれる
ビザンチンノードは、ハッシュグラフに任意のEdgeとVerticleを追加できる
ハッシュの衝突は(ハッシュ関数の衝突耐性により)作れないので、正しいノードたちが更新のセットを送り合うのを妨げることはできない
たくさんのHeadとかを作るかもしれないけど、これらの更新は別にアルゴリズムの正しさに影響与えないよね ← だってHeadだもんね。過去を書き換えるわけでもないしkekeho.icon
というわけで、最終的にはすべての正しいノードたちが、他の正しいノードを介して直接・間接的に、最終的に他のすべての正しいノードと通信できるという仮定さえ置けば、配信を保証できる
Unique ID
ID、多くの既存CRDTでは各ノードに信頼をおいて作っている
ビザンチンノードが同じ更新IDを持つ異なる更新を作れちゃったりして、まずいよね
更新のID: $ H(u)
更新の有効性検証
与えられた更新が有効かどうか、全ての正しいノードが合意すること(=> 収束)が必要
BFTの証明
収束するのはうれCkekeho.icon
参考
まだ観てないけど謎の勉強会の動画があった: https://www.youtube.com/watch?v=KjvPz7Pf33U